<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3835：[Poi2014]Supercomputer</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Supercomputer</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Supercomputer</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Poi2014]Supercomputer                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>Byteasar has designed a supercomputer of novel architecture. It may comprise of many (identical) processing units. Each processing unit can execute a single instruction per time unit.</div>
<div>The programs for this computer are not sequential but rather have a tree structure. Each instruction may have zero, one, or multiple subsequent instructions, for which it is the parent instruction.</div>
<div>The instructions of the program can be executed in parallel on all available processing units. Moreover, they can be executed in many orders: the only restriction is that an instruction cannot be executed unless its parent instruction has been executed before. For example, as many subsequent instructions of an instruction that has been executed already can be executed in parallel as there are processing units.</div>
<div>Byteasar has a certain program to run. Since he likes utilizing his resources optimally, he is wondering how the number of processing units would affect the running time. He asks you to determine, for a given program and number of processing units, the minimum execution time of the program on a supercomputer with this many processing units.</div>
<div></div>
<div>
<div>给定一棵N个节点的有根树，根节点为1。</div>
<div>Q次询问，每次给定一个K，用最少的操作次数遍历完整棵树，输出最少操作次数。</div>
<div>每次操作可以选择访问不超过K个未访问的点，且这些点的父亲必须在之前被访问过。</div>
</div>
<p></p></p><hr/><h3>输入格式</h3><p><div>In the first line of standard input, there are two integers, N and Q （1&lt;=N,Q&lt;=1 000 000）, separated by a single space, that specify the number of instructions in Byteasar's program and the number of running time queries (for different numbers of processing units).</div>
<div>In the second line of input, there is a sequence of Q integers, K1,k2,&hellip;Kq (1&lt;=Ki&lt;=1 000 000), separated by single spaces: Ki is the number of processing units in Byteasar's i-th query.</div>
<div>In the third and last input line, there is a sequence of N-1 integers, A2,A2&hellip;An (1&lt;=Ai&lt;i), separated by single spaces: Ai specifies the number of the parent instruction of the instruction number i. The instructions are numbered with successive integers from 1 to N, where the instruction no. 1 is the first instruction of the program.</div>
<p></p></p><hr/><h3>输出格式</h3><p><div>
<div>Your program should print one line consisting of Q integers, separated by single spaces, to the standard output: the i-th of these numbers should specify the minimum execution time of the program on a supercomputer with Ki processing units.</div>
</div>
<p></p></p><hr/><h3>样例输入</h3><pre>20 1
3
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11
</pre><hr/><h3>样例输出</h3><pre>8</pre><hr/><h3>提示</h3><p><div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>
<div>6</div>
<div>7</div>
<div>8</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>1<span class="Apple-tab-span" style="white-space:pre">	</span> <span class="Apple-tab-span" style="white-space:pre">	</span>&nbsp;</div>
<div>2<span class="Apple-tab-span" style="white-space:pre">	</span>3<span class="Apple-tab-span" style="white-space:pre">	</span>4</div>
<div>5<span class="Apple-tab-span" style="white-space:pre">	</span>6<span class="Apple-tab-span" style="white-space:pre">	</span>7</div>
<div>8<span class="Apple-tab-span" style="white-space:pre">	</span>10<span class="Apple-tab-span" style="white-space:pre">	</span>&nbsp;</div>
<div>9<span class="Apple-tab-span" style="white-space:pre">	</span>12<span class="Apple-tab-span" style="white-space:pre">	</span>&nbsp;</div>
<div>11<span class="Apple-tab-span" style="white-space:pre">	</span>13<span class="Apple-tab-span" style="white-space:pre">	</span>14</div>
<div>15<span class="Apple-tab-span" style="white-space:pre">	</span>16<span class="Apple-tab-span" style="white-space:pre">	</span>17</div>
<div>18<span class="Apple-tab-span" style="white-space:pre">	</span>19<span class="Apple-tab-span" style="white-space:pre">	</span>20</div>
<div></div>
<p></p></p><hr/><h3>题目来源</h3><p>鸣谢 Claris</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3835" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3835" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>